package main

import "fmt"

/*
给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
返回一个由上述 k 部分组成的数组。
*/
func main() {
	list := ListNode{1, nil}
	res := splitListToParts(&list, 6)
	for _, v := range res {
		fmt.Printf("%#v\n", v)
	}

}

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 *	splitListToParts
 *	@Description: 动态规划
 *	@param head *ListNode
 *	@param k int
 *	@return res []*ListNode
 */
func splitListToParts(head *ListNode, k int) (res []*ListNode) {
	n := 0
	for tmpHead := head; tmpHead != nil; tmpHead = tmpHead.Next {
		n++
	}
	res = make([]*ListNode, 0)
	for ; k != 0; k-- {
		num := 0
		if k >= n {
			num = 1
			n -= 1
		} else if n%k != 0 {
			num = n/k + 1
			n -= num
		} else {
			num = n / k
			n -= num
		}
		tmpHead := head
		node := head
		for ; num != 0; num-- {
			if head == nil {
				break
			}
			node = head
			head = head.Next
		}
		if node != nil {
			node.Next = nil
		}
		res = append(res, tmpHead)
	}
	return res
}
